1. Field of Invention
My invention relates to digital halftoning, specifically to the distribution of monochrome pixels within a digital halftone cell.
2. Description of Prior Art
Digital halftoning seeks to render complex images using a monochrome bitmap. Within this graph paper-like grid, each square picture element or pixel is designated one of two “colors.” Said colors are usually (but not limited to) black and white. Each pixel then may be represented by the binary numbers 0 or 1.
A reproduction of an input image appears when human vision fails to distinguish the monochrome pixels. This usually occurs when viewing from a distance. The eye “averages” a group of black and white pixels and interprets it as a level of gray.
The smallest square grouping at which this phenomenon occurs measures two-pixels-by-two-pixels. This four pixel area or cell may depict five levels of gray: 1.) all four pixels black; 2,) three black and one white; 3.) two black and two white; 4.) one black and three white; and 5.) all four white. These five gray levels may be nominally interpreted as 0%, 25%, 50%, 75%, and 100% white, occurring in increments of approximately 25%.
The four corresponding pixels of a 1:1 input bitmap most often are captured at a greater binary pixel-depth. At an arbitrary 8-bits per pixel, each pixel may display a gray level range of 0–255. The four-pixel-cell may display a gray level range of 0–1020. This translates into 1021 gray levels in increments of approximately 0.1%.
Comparing specific corresponding four-pixel-cell input and output gray levels, this reduction of 1020 levels to five levels will yield a difference or rounding error. A method developed by Robert W. Floyd, et al, published in “An Adaptive Algorithm for Spatial Grayscale,” (Proceeding of the S.I.D. vol. 17/2 Second Quarter [1976] pp. 75–76) is to take this error and spread or “diffuse” it to adjoining input cells. Known as Floyd and Steinberg “error diffusion,” the method has become the prevailing method used throughout the digital halftoning industry today.
A problem with error diffusion is that it works well when the errors to be diffused are relatively large. However, when the errors are relatively small, the method allows them to accumulate until they “drop” many cells away from where they first occurred. The result is an artifact, usually in a serpentine shape, that compromises the grayscale accuracy of the output image. Floyd, et al, does not teach how to use all of the input image's pixels to determine the “color” of individual output pixels.
In my previous U.S. patent, “Method for Reproducing an Image” (Case, U.S. Pat. No. 6,002,493 [1999]), I developed a method for pattern selection of monochrome pixels within a cell. In applying my pattern method, I encountered the same rounding error problem that error diffusion seeks to address. Without diffusion of the rounding errors, the size of the output cell dictates the global image's grayscale.
If a four-pixel-by-four-pixel input cell is used at a 1:1 ratio to derive a four-pixel-by-four pixel output cell, the global image will be restricted to just 17 gray levels. They include all black plus the incremental addition of 16 individual white pixels per cell. At a two-pixel-by-two-pixel cell, the global image will be restricted to just 5 gray levels. They include all black plus the incremental addition of 4 individual white pixels per cell. While Case does teach how to determine the “color” of pixels within a digital halftone cell, it does not teach how to use all of the input image's pixels to determine the output monochrome gray level of each cell.
In error diffusion, micro elements are used to determine macro elements. Local monochrome gray levels effectively determine the global monochrome gray levels. In such a scenario, the influences of various micro elements will clash, causing the macro elements to stray from the task of accurately reproducing the input bitmap.